package 剑指Offer.简单;

import Entity.TreeNode;

/**
 * 输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
 *
 * 例如：
 *
 * 给定二叉树 [3,9,20,null,null,15,7]，
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 * 返回它的最大深度3 。
 * 
 * @author caihe
 * @date 2022/8/29 8:55
 */
public class _55I二叉树的深度 {

    int deep = 0;
    public int maxDepth(TreeNode root) {
        dfs(root, 0);
        return deep;
    }
    
    private void dfs(TreeNode node, int count) {
        if (node == null) {
            deep = Math.max(count, deep);
            return;
        }
        dfs(node.left, count + 1);
        dfs(node.right, count + 1);
    }
    
    
    public int maxDepthV2(TreeNode root) {
        if (root == null){
            return 0;
        }
        return Math.max(maxDepthV2(root.left), maxDepthV2(root.right)) + 1;
    }
    
}
